package ClassLib;

import javax.imageio.ImageTranscoder;
import java.util.*;
import java.util.stream.Collector;
import java.util.stream.Collectors;

public class libof202410_1 {
    //https://leetcode.cn/problems/swap-nodes-in-pairs/
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode reverseNodes = swapPairs(head.next.next);
        ListNode next = head.next;
        next.next = head;
        head.next = reverseNodes;
        return next;
    }

    //https://leetcode.cn/problems/reverse-nodes-in-k-group/
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null) return head;
        ListNode p = head;
        for (int i = 0; i < k; i++) {
            if (p == null) return head;
            p = p.next;
        }

        //reverse head->p
        ListNode dummy = new ListNode(0);
        ListNode cur = head;
        while (cur != p) {
            ListNode next = cur.next;
            cur.next = dummy.next;
            dummy.next = cur;
            cur = next;
        }
        ListNode reverse = reverseKGroup(p, k);
        head.next = reverse;
        return dummy.next;
    }

    //https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (head != null) {
            int val = head.val;

            if (head.next != null && val == head.next.val) {
                while (head != null && head.val == val) head = head.next;
            } else {
                cur.next = head;
                head = head.next;
                cur = cur.next;
            }
        }
        cur.next = null;
        return dummy.next;
    }

    //https://leetcode.cn/problems/reverse-linked-list-ii/
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == 1) return reverseN(head, right);
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }

    private ListNode reverseN(ListNode head, int n) {
        if (head == null || head.next == null) return head;
        ListNode start = head;
        for (int i = 0; i < n; i++) {
            if (start == null) break;
            start = start.next;
        }
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        ListNode p = head;
        while (p != start) {
            ListNode next = p.next;
            p.next = cur.next;
            cur.next = p;
            p = next;
        }
        head.next = start;
        return dummy.next;
    }

    //https://leetcode.cn/problems/palindrome-linked-list/
    private ListNode start;

    public boolean isPalindrome(ListNode head) {
        start = head;
        return traversePalindrome(head);
    }

    private boolean traversePalindrome(ListNode tail) {
        if (tail == null) return true;
        boolean res = traversePalindrome(tail.next) && tail.val == start.val;
        start = start.next;
        return res;
    }

    //https://leetcode.cn/problems/range-sum-query-immutable/
    class NumArray {
        int[] sumArray;

        public NumArray(int[] nums) {
            sumArray = new int[nums.length + 1];
            for (int i = 1; i <= nums.length; i++) {
                sumArray[i] = sumArray[i - 1] + nums[i - 1];
            }
        }

        public int sumRange(int left, int right) {
            return sumArray[right + 1] - sumArray[left];
        }
    }

    //https://leetcode.cn/problems/range-sum-query-2d-immutable/
    class NumMatrix {
        int[][] sumMatrix;
        public NumMatrix(int[][] matrix) {
            sumMatrix = new int[matrix.length + 1][matrix[0].length + 1];
            for (int i = 1; i < sumMatrix.length; i++) {
                for (int j = 1; j < sumMatrix[0].length; j++) {
                    sumMatrix[i][j] = sumMatrix[i - 1][j]
                            + sumMatrix[i][j - 1]
                            - sumMatrix[i - 1][j - 1]
                            + matrix[i - 1][j - 1];
                }
            }
        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            return sumMatrix[row2 + 1][col2 + 1]
                    - sumMatrix[row2 + 1][col1]
                    - sumMatrix[row1][col2 + 1]
                    + sumMatrix[row1][col1];
        }
    }
    //   //https://leetcode.cn/problems/matrix-block-sum/
    class SolutionofMatrixBlockSum {
        public int[][] matrixBlockSum(int[][] mat, int k) {
            int[][] sumMatrix;
            sumMatrix = new int[mat.length + 1][mat[0].length + 1];
            for (int i = 1; i < sumMatrix.length; i++) {
                for (int j = 1; j < sumMatrix[0].length; j++) {
                    sumMatrix[i][j] = sumMatrix[i - 1][j]
                            + sumMatrix[i][j - 1]
                            - sumMatrix[i - 1][j - 1]
                            + mat[i - 1][j - 1];
                }
            }
            int m=mat.length;
            int n=mat[0].length;
            int[][] ans=new int[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    ans[i][j]=sumRegion(sumMatrix, Math.max(0,i-k), Math.max(0,j-k), Math.min(m-1,i+k), Math.min(n-1,j+k));
                }
            }
         return ans;
        }
        private int sumRegion(int[][] sumMatrix,int row1, int col1, int row2, int col2) {
            return sumMatrix[row2 + 1][col2 + 1]
                    - sumMatrix[row2 + 1][col1]
                    - sumMatrix[row1][col2 + 1]
                    + sumMatrix[row1][col1];
        }
    }


    class SolutionofFindSmallestRegion {
        //https://leetcode.cn/problems/smallest-common-region/
        //plus 下面的做法虽然对，但是根本无需引入一个tree 数据结构，只需要使用map 管理子父节点的关系即可
//   给你一些区域列表 regions ，每个列表的第一个区域都包含这个列表内所有其他区域。
//
//    很自然地，如果区域 X 包含区域 Y ，那么区域 X  比区域 Y 大。
//
//    给定两个区域 region1 和 region2 ，找到同时包含这两个区域的 最小 区域。
//
//    如果区域列表中 r1 包含 r2 和 r3 ，那么数据保证 r2 不会包含 r3 。
//
//    数据同样保证最小公共区域一定存在。
//
//
//
//    示例 1：
//
//    输入：
//    regions = [["Earth","North America","South America"],
//            ["North America","United States","Canada"],
//            ["United States","New York","Boston"],
//            ["Canada","Ontario","Quebec"],
//            ["South America","Brazil"]],
//    region1 = "Quebec",
//    region2 = "New York"
//    输出："North America"
        public String findSmallestRegion(List<List<String>> regions, String region1, String region2) {
            //基本思路其实和树找公共祖先节点是一个道理
            HashMap<String, Tree<String>> treeHashMap = buildRegionTreeNodes(regions);
            Tree<String> treeRegion1 = treeHashMap.get(region1);
            Tree<String> treeRegion2 = treeHashMap.get(region2);
            Tree<String> t1 = treeRegion1;
            Tree<String> t2 = treeRegion2;
            while (t1 != t2) {
                if (t1 == null) t1 = treeRegion2;
                else t1 = t1.parent;
                if (t2 == null) t2 = treeRegion1;
                else t2 = t2.parent;
            }
            return t1.val;
        }

        private HashMap<String, Tree<String>> buildRegionTreeNodes(List<List<String>> regions) {
            HashMap<String, Tree<String>> map = new HashMap<>();
            for (List<String> region : regions) {
                String parent = region.get(0);
                map.putIfAbsent(parent, new Tree<>(parent));
                for (int i = 1; i < region.size(); i++) {
                    String child = region.get(i);
                    map.putIfAbsent(child, new Tree<>(child));
                    map.get(child).parent = map.get(parent);
                }
            }
            return map;
        }

        class Tree<T> {
            T val;
            Tree left;
            Tree right;
            Tree parent;

            public Tree() {
            }

            public Tree(T val) {
                this.val = val;
            }
        }
    }
    //https://leetcode.cn/problems/maximum-size-subarray-sum-equals-k/
    /**
     *   给定一个数组 nums 和一个目标值 k，找到和等于 k 的最长连续
     *             子数组
     *     长度。如果不存在任意一个符合要求的子数组，则返回 0。
     *
     *
     *
     *     示例 1:
     *
     *     输入: nums = [1,-1,5,-2,3], k = 3
     *     输出: 4
     *     解释: 子数组 [1, -1, 5, -2] 和等于 3，且长度最长。
     *     示例 2:
     *
     *     输入: nums = [-2,-1,2,1], k = 1
     *     输出: 2
     *     解释: 子数组 [-1, 2] 和等于 1，且长度最长。
     */

    class SolutionofMaxSubArrayLen {
        public int maxSubArrayLen(int[] nums, int k) {
              int[] sumArr=new int[nums.length+1];
            int ans=Integer.MIN_VALUE;
            HashMap<Integer,Integer> map=new HashMap<>();
            for (int i = 1; i < sumArr.length; i++) {
                sumArr[i]=sumArr[i-1]+nums[i-1];
            }
            for (int i = 0; i < sumArr.length; i++) {
                //下面的实现可以换成hash的方式，能不能彻底理解？
                map.putIfAbsent(sumArr[i],i);
                if (map.containsKey(sumArr[i] - k))
                    ans = Math.max(ans, i - map.get(sumArr[i] - k));
//                for (int j = 0; j < i; j++) {
//
//                    if(sumArr[i]-k==sumArr[j]){
//                        ans=Math.max(ans,i-j);
//                    }
//                }
            }
            return ans==Integer.MIN_VALUE?0:ans;
        }

    }
    //https://leetcode.cn/problems/subarray-sum-equals-k/
    public int subarraySum(int[] nums, int k) {
        int[] sumArr=new int[nums.length+1];
        int ans=0;
        HashMap<Integer,Integer> map=new HashMap<>();
        map.put(0,1);
        for (int i = 1; i < sumArr.length; i++) {
            sumArr[i]=sumArr[i-1]+nums[i-1];
            //下面的实现可以换成hash的方式，能不能彻底理解？
            ans+=map.getOrDefault(sumArr[i]-k,0);
            //这个hashmap 的意思是前缀和作为key，前缀和出现的频次作为值
            map.put(sumArr[i],map.getOrDefault(sumArr[i],0)+1);
        }
        return ans;
    }
    //https://leetcode.cn/problems/count-of-range-sum/
    class SolutionofCountRangeSum {
        private long[] temp;
        private int count;
        private int lower;
        private int upper;

        public int countRangeSum(int[] nums, int lower, int upper) {

//    //还是要区间和的思路去做
//        long[] preSum=new long[nums.length+1];
//        int ans=0;
//        for (int i = 1; i < preSum.length; i++) {
//            preSum[i]=preSum[i-1]+nums[i-1];
//        }
//        for (int i = 0; i < preSum.length; i++) {
//            for (int j = 0; j <i; j++) {
//                long rangeSum= preSum[i]-preSum[j];
//                if(rangeSum>=lower && rangeSum<=upper){
//                    ans++;
//                }
//            }
//        }
//        return ans;
            //还是要区间和的思路去做
//        long[] preSum=new long[nums.length+1];
//        int ans=0;
//        for (int i = 1; i < preSum.length; i++) {
//            preSum[i]=preSum[i-1]+nums[i-1];
//        }
//        for (int i = 0; i < preSum.length; i++) {
//            //看到下面有点熟悉了，这里需要让j 遍历n次，然后累计值，我们之前做过一道题，就是这个 https://leetcode.cn/problems/count-of-smaller-numbers-after-self/description/
//            long sumjLower= preSum[i]-lower;
//            long sumjUpper=preSum[i]-upper;
//            for (int j = 0; j <i; j++) {
//                if(sumjLower>= preSum[j]&&  sumjUpper <=preSum[j]){
//                    ans++;
//                }
//            }
//        }
//        return ans;
//区间和的思路加上 归并排序的思路
            long[] preSum=new long[nums.length+1];
            int ans=0;
            for (int i = 1; i < preSum.length; i++) {
                preSum[i]=preSum[i-1]+nums[i-1];
            }
            this.lower = lower;
            this.upper = upper;
            temp=new long[preSum.length];
            sort(preSum,0,preSum.length-1);
            return count;
        }

        private void sort(long[] nums, int lo, int hi) {
            if(lo>=hi) return;
            int mid=lo+(hi-lo)/2;
            sort(nums,lo,mid);
            sort(nums,mid+1,hi);
            merge(nums,lo,mid,hi);
        }

        private void merge(long[] nums, int lo, int mid, int hi) {
            if(lo>=hi) return;
            int start=mid+1,end=mid+1;
            for (int i=lo;i<=mid;i++) {
                while (start<=hi&& nums[start]-nums[i]<lower) start++;
                while (end<=hi&& nums[end]-nums[i]<=upper) end++;
                count+=end-start;
            }
            int i=lo,j=mid+1;
            int k=lo;
            for (;k<=hi;k++) temp[k] = nums[k];
            k=lo;
            while (k<=hi){
                if (i==mid+1) nums[k++]=temp[j++];
                else if(j==hi+1) nums[k++]=temp[i++];
                else if(temp[i]<=temp[j]) {
                    nums[k++]=temp[i++];
                }
                else{
                    nums[k++]=temp[j++];
                }
            }
        }
    }

    //https://leetcode.cn/problems/count-of-smaller-numbers-after-self/
    public List<Integer> countSmaller(int[] nums) {

        //计算右侧比nums[i] 小的值
        int[] ans=new int[nums.length];
        int[][] numsWithidx=new int[nums.length][2];
        for (int i = 0; i < numsWithidx.length; i++) {
            numsWithidx[i][0]=nums[i];
            numsWithidx[i][1]=i;
        }
        mergeSort(numsWithidx,0,nums.length-1,new int[nums.length][2],ans);
        ArrayList<Integer> list = new ArrayList<>();
        for (int num : ans) list.add(num);
        return list;
    }

    private void mergeSort(int[][]nums, int lo, int hi,  int[][]temp,  int[] ans ) {
        if(lo>=hi) return;
        int mid=lo+(hi-lo)/2;
        mergeSort(nums,lo,mid,temp,ans);
        mergeSort(nums,mid+1,hi,temp,ans);
        merge(nums,lo,mid,hi,temp,ans);
    }

    private void merge(int[][] nums, int lo, int mid, int hi, int[][] temp,int[] ans) {
        if(lo>=hi) return;
        int i=lo,j=mid+1;
        int k=lo;
        for(;k<=hi;k++) {
            temp[k]=nums[k];
        }
        k=lo;
        while(k<=hi){
           if(j==hi+1) {
               ans[temp[i][1]]+=j-mid-1;
               nums[k++]=temp[i++];
           }
           else if(i==mid+1) nums[k++]=temp[j++];
           else if(temp[i][0]<=temp[j][0]) {
               ans[temp[i][1]]+=j-mid-1;
               nums[k++] = temp[i++];
           }
           else nums[k++] = temp[j++];
        }
    }
    //https://leetcode.cn/problems/product-of-the-last-k-numbers/
    class ProductOfNumbers {
        ArrayList<Long> preMultiplication;
        public ProductOfNumbers() {
          preMultiplication = new ArrayList<>();
          preMultiplication.add(1L);
        }

        public void add(int num) {
          if(num==0) {
              preMultiplication.clear();
              preMultiplication.add(1L);
              return;
          }
          preMultiplication.add(preMultiplication.get(preMultiplication.size()-1)* num);
        }

        public int getProduct(int k) {
          if(preMultiplication.size()-1<k) return 0;
          return (int) (preMultiplication.get(preMultiplication.size()-1) / preMultiplication.get(preMultiplication.size()-1-k));
        }
    }

    //https://leetcode.cn/problems/gou-jian-cheng-ji-shu-zu-lcof/
    class SolutionofStatisticalResult {
        public int[] statisticalResult(int[] arrayA) {
            //最容易想到的，但是没有考虑到0的情况
//            int aggr = 1;
//            int[] ans = new int[arrayA.length];
//            for (int num : arrayA) aggr *= num;
//            for (int i = 0; i < arrayA.length; i++) {
//                ans[i] = aggr / arrayA[i];
//            }
//            return ans;
            //自己实现的，比较直观
//            int aggr=1;
//            HashSet<Integer> set = new HashSet<>();
//            int[] ans=new int[arrayA.length];
//            for (int i = 0; i < arrayA.length; i++) {
//                int num = arrayA[i];
//                if (num == 0) {
//                    set.add(i);
//                    continue;
//                }
//                aggr *= num;
//            }
//            for (int i = 0; i < arrayA.length; i++) {
//               if(set.size()==0)
//                   ans[i]=aggr/arrayA[i];
//               else if(set.size()>1 || !set.contains(i)){
//                   ans[i]=0;
//               }
//               else{
//                   ans[i]=aggr;
//               }
//            }
//            return ans;
            //使用前缀后缀积来做
            int n= arrayA.length;
            if(n==0) return new int[0];
            int[] prefix=new int[n];
            int[] suffix=new int[n];
            for (int i = 0; i < n; i++) {
                prefix[i]=(i-1<0?1: prefix[i-1])*arrayA[i];
            }
            for (int i = n-1; i >= 0; i--) {
                suffix[i]=(i+1>=n?1: suffix[i+1])*arrayA[i];
            }
            int[] ans=new int[n];
            ans[0]=suffix[1];
            ans[n-1]=prefix[n-2];
            for (int i = 1; i < n-1; i++) {
                ans[i]=suffix[i+1]* prefix[i-1];
            }
            return ans;
        }
    }
    //https://leetcode.cn/problems/car-pooling/
    class SolutionofCarPolling {
        public boolean carPooling(int[][] trips, int capacity) {
            DiffArray diffArray=new DiffArray(new int[1000]);
            for (int[] trip : trips) {
                int num = trip[0];
                int i = trip[1];
                int j = trip[2]-1;
               diffArray.add(num,i,j);
            }
            for (int num : diffArray.get()) {
                if(num>capacity) return false;
            }
            return true;
        }
        class DiffArray{
            private  int[] diffNums;

            public DiffArray(int[] nums){
                diffNums=new int[nums.length];
                diffNums[0]=nums[0];
                for (int i = 1; i < nums.length; i++) {
                    diffNums[i]=nums[i]-nums[i-1];
                }

            }
            public void add(int num,int i,int j){
                diffNums[i] += num;
                if (j < diffNums.length - 1)
                    diffNums[j + 1] -= num;
            }
            public int[] get(){
                int[] ans=new int[diffNums.length];
                ans[0]=diffNums[0];
                for (int i = 1; i < diffNums.length; i++) {
                    ans[i]=ans[i-1]+diffNums[i];
                }
                return ans;
            }
        }
    }
    //https://www.douyu.com/topic/PUBGJKZLX?rid=4520630&dyshid=94eb67-9ceb9406dc263c47784da1c100021501
    public int minInsertions(String s) {
      //做这一道题一定要先做单括号的，然后在单括号的基础上发展成右边双括号的
        int need=0,res=0;
        for (char c : s.toCharArray()) {
            if(c=='('){
                if(need%2==1){
                    res++;
                    need--;
                }
                need+=2;
            }
            else if(c==')') {
                need--;
                if(need<0){
                    res++;
                    need=1;
                }

            }
        }
        return  res+need;
    }
  //https://leetcode.cn/problems/longest-valid-parentheses/
    public int longestValidParentheses(String s) {
        //用滑动窗口不好做
//        int left=0,right=0;
//        int left_p=0,right_p=0;
//        int ans=0;
//        while (right<s.length()) {
//            char r_c = s.charAt(right++);
//            if(r_c=='(') left_p++;
//            else if(r_c==')') right_p++;
//            while (left_p<right_p) {
//                char l_c = s.charAt(left++);
//                if(l_c=='(') left_p--;
//                else if(l_c==')') right_p--;
//            }
//            int giveup=left_p-right_p;
//            ans= Math.max(ans,right-left-giveup);
//        }
//
//        return ans;
        Stack<Integer> stk=new Stack<>();
        int ans=0;
        int[] dp=new int[s.length()];
        char[] charArray = s.toCharArray();
        for (int i = 0; i < charArray.length; i++) {
            char c = charArray[i];
            if (c == '(') {
                stk.push(i);
            } else {
                if (!stk.isEmpty()) {
                    Integer left_index = stk.pop();
                    dp[i]=  i+1-left_index+ (left_index>0?dp[left_index-1]:0);
                    ans = Math.max(ans, +dp[i]);
                }
            }
        }
        return  ans;
    }
    //https://leetcode.cn/problems/sliding-window-maximum/
    class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
          int[] ans=new int[nums.length-k+1];
          MonitorQueue queue=new MonitorQueue();
          //填充k-1 个值
            int i=0;
            for (; i <k-1; i++) {
                queue.add(nums[i]);
            }
            int idx=0;
            for (;i<nums.length;i++){
                queue.add(nums[i]);
                //logic
                ans[idx++]= queue.max();
                queue.remove(nums[i-k+1]);
            }
            return ans;
        }
        // 这个队列能够获取队列内的最大值
        class  MonitorQueue{
            LinkedList<Integer> queue;
            MonitorQueue(){
                queue=new LinkedList<>();
            }
            public int size(){
                return queue.size();
            }
            public int max(){
                return queue.getFirst();
            }
            public void remove(Integer val){
                if(queue.getFirst().equals(val)){
                    queue.removeFirst();
                }
            }
            public void add(int val){
                while (!queue.isEmpty() && queue.getLast()<val) queue.removeLast();
                queue.addLast(val);
            }
        }
    }
    //https://leetcode.cn/problems/simplify-path/
    public String simplifyPath(String path) {
        //真的蠢，一点灵性都没有
//        LinkedList<Character> stack=new LinkedList<>();
//        char[] charArray = path.toCharArray();
//        stack.addLast(charArray[0]);
//        for (int i = 1; i < charArray.length; i++) {
//            char c = charArray[i];
//            if(c=='.'&& charArray[i-1]!='.' && (i+2<charArray.length&& charArray[i+1]=='.'&& charArray[i+2]=='/' )) {
//               if(stack.size()>1){
//                   do {
//                       stack.removeLast();
//                   } while (!stack.isEmpty() && stack.getLast() != '/');
//               }
//                i++;
//                continue;
//            }
//            if(c=='.'&& charArray[i-1]!='.'&&(i+1<charArray.length&&charArray[i+1]=='/')) {
//                i++;
//                continue;
//            }
//            stack.addLast(c);
//        }
//        StringBuilder sb = new StringBuilder();
//        while (!stack.isEmpty()) {
//            Character elem = stack.removeFirst();
//            if(!sb.isEmpty() && elem=='/'&&sb.charAt(sb.length()-1)=='/') continue;
//            if(!sb.isEmpty()&& stack.isEmpty()&&elem=='/') continue;
//            sb.append(elem);
//        }
//        return sb.toString();
        String[] parts = path.split("/");
        Stack<String> stk=new Stack<>();
        for (String part : parts) {
            if(part.isEmpty()|| part.equals(".")) continue;
            else if(part.equals("..")){
                if(!stk.isEmpty())
                 stk.pop();
            }
            else stk.push(part);
        }
      String res= "";
        while (!stk.isEmpty()) {
            res="/"+ stk.pop()+res;
        }
        return res.isEmpty()?"/":res;
    }
  //https://leetcode.cn/problems/min-stack/
    class MinStack {

        Stack<Integer> stack1;
        Stack<Integer> stack2;
        public MinStack() {

            stack1=new Stack<>();
            stack2=new Stack<>();
        }

        public void push(int val) {
           stack1.push(val);
           if(stack2.isEmpty()||stack2.peek()>=val) stack2.push(val);
        }

        public void pop() {
            Integer pop = stack1.pop();
            if(stack2.peek().equals(pop)) stack2.pop();
        }

        public int top() {
          return stack1.peek();
        }

        public int getMin() {
          return  stack2.peek();
        }
    }
    //https://leetcode.cn/problems/kth-largest-element-in-an-array/
    public int findKthLargest(int[] nums, int k) {
      //可以利用快排的思想
        int lo=0,hi=nums.length-1;
        k = hi - k + 1;
        while (lo <= hi) {
            //这个k代表的是第k小元素的索引
            int p = partition(nums, lo, hi);
            if (p == k) return nums[p];
            else if (p < k) {
                lo = p + 1;
            } else {
                hi = p - 1;
            }
        }
          return -1;
    }

    private int partition(int[] nums, int lo, int hi) {
        int pivot=nums[lo];
        int i=lo+1,j=hi;
        while (i<=j){
            while (i<=j&&nums[i]<=pivot) i++;
            while (i<=j&&nums[j]>=pivot) j--;
            if (i < j)
                swap(nums, i, j);
        }
        swap(nums,lo,j);
        return j;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp=nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    }
    //https://leetcode.cn/problems/top-k-frequent-elements/
    public int[] topKFrequent(int[] nums, int k) {
       Map<Integer,Integer> map=new HashMap<>();
       for (int num : nums) {
           map.put(num,map.getOrDefault(num,0)+1);
       }
       PriorityQueue<Integer[]> pq= new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
       map.forEach((key,val)->{
           pq.offer(new Integer[]{key,val});
           if(pq.size()>k) pq.poll();
       });
       int[] ans=new int[k];
       int i=0;
       while (!pq.isEmpty()){
           Integer[] poll = pq.poll();
           ans[i++]=poll[0];
       }
       return ans;
    }
    /**
     * Your MinStack object will be instantiated and called as such:
     * MinStack obj = new MinStack();
     * obj.push(val);
     * obj.pop();
     * int param_3 = obj.top();
     * int param_4 = obj.getMin();
     */

//    给定一个二进制数组nums和一个整数k，如果可以翻转最多k个0，则返回数组中连续 1 的最大个数 。
//
//    示例 1：
//    输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
//    输出：6
//    解释：[1,1,1,0,0,1,1,1,1,1,1]
//    数组下标5和10的数字从 0 翻转到 1，最长的子数组长度为 6。
//
//    示例 2：
//    输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
//    输出：10
//    解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
//    数组下标4、5、9数字从 0 翻转到 1，最长的子数组长度为 10。
//
//            1 <= nums.length <= 105
//    nums[i] 不是 0 就是 1
//            0 <= k <= nums.length

    public int longestOnes(int[] nums, int k) {
        int ans=0;
       int left=0,right=0;
       int zero_count=0;
       while (right<nums.length) {
           int r=nums[right++];
           if(r==0) zero_count++;
           while (zero_count>k){
               int l=nums[left++];
               if(l==0) zero_count--;
           }
           ans= Math.max(ans,right-left);
       }
       return ans;
    }
 //https://leetcode.cn/problems/kth-largest-element-in-a-stream/
    class KthLargest {
     private final int k;
     PriorityQueue<Integer> pq=new PriorityQueue<>();
        public KthLargest(int k, int[] nums) {
            this.k = k;
            for (int num : nums) {
                pq.offer(num);
                if(pq.size()>k) pq.poll();
            }
        }

        public int add(int val) {
             pq.offer(val);
            if(pq.size()>k) pq.poll();
            return pq.peek();
        }
    }
  //https://leetcode.cn/problems/find-median-from-data-stream/
    class MedianFinder {
        PriorityQueue<Integer> pq_smail=new PriorityQueue<>();
        PriorityQueue<Integer> pq_large=new PriorityQueue<>((a,b)-> b-a);
        public MedianFinder() {

        }

        public void addNum(int num) {
         if(pq_smail.size()>=pq_large.size()){
             pq_smail.offer(num);
             pq_large.offer(pq_smail.poll());
         }
         else{
             pq_large.offer(num);
             pq_smail.offer(pq_large.poll());
         }

        }

        public double findMedian() {

           if(pq_large.size()>pq_smail.size()){
               return pq_large.peek();
           }
           if(pq_large.size()<pq_smail.size()){
               return pq_smail.peek();
           }
           return (pq_large.peek()+pq_smail.peek())/2d;
        }
    }
  //https://leetcode.cn/problems/sort-characters-by-frequency/
    public String frequencySort(String s) {
       Map<Character,Integer> map=new HashMap<>();
       PriorityQueue<Object[]> pq=new PriorityQueue<>((a,b)->(int)b[1]-(int)a[1]);
        for (char c : s.toCharArray()) {
            map.put(c,map.getOrDefault(c,0)+1);
        }
        map.forEach((key,val)->{
            pq.offer(new Object[]{key,val});
        });
        StringBuilder sb=new StringBuilder();
        while (!pq.isEmpty()){
            Object[] poll=pq.poll();
            int freq=(int) poll[1];
            for (int i = 0; i <freq ; i++) {
                sb.append((char) poll[0]);
            }
        }
        return sb.toString();
    }
    //有N件物品和一个最多能背重量为W的背包（也就是说背包的容量是W），第i件物品的重量是weight[i]，其价值是value[i]，每件物品只能背一次，求解将哪些物品放到背包里面物品价值的总和最大。
    public int pack(int[] weight,int[] value, int target){
        int n=weight.length;
        int[][] dp=new int[n+1][target+1];
        //base case
        //none
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= target; j++) {
                dp[i][j] =dp[i-1][j];
                if(j-weight[i-1]>=0){
                    dp[i][j] =Math.max(dp[i][j],dp[i-1][j-weight[i-1]]+value[i-1]);
                }
            }
        }
        return dp[n][target];
    }

    //https://leetcode.cn/problems/top-k-frequent-words/
    public List<String> topKFrequent(String[] words, int k) {
      Map<String,Integer[]> map=new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            if (map.containsKey(word)) {
                 map.get(word)[0]++;
            } else {
                map.put(word, new Integer[]{1, i});
            }
        }
        PriorityQueue<Map.Entry<String,Integer[]>> pq=new PriorityQueue<>((a,b)->{
            if(a.getValue()[0].equals(b.getValue()[0])){
                return b.getKey().compareTo(a.getKey());
            }
            else{
                return a.getValue()[0].compareTo(b.getValue()[0]);
            }
        });
        for (Map.Entry<String, Integer[]> set : map.entrySet()) {
            pq.offer(set);
            if(pq.size()>k) pq.poll();
        }
        LinkedList<String> ans=new LinkedList<>();
        while (!pq.isEmpty()){
            ans.addFirst(pq.poll().getKey());
        }
        return ans;
    }
    //https://leetcode.cn/problems/single-threaded-cpu/
    public int[] getOrder(int[][] tasks) {
     // 这个map的key 是每个时刻，value 是每个时刻每个任务的优先级
        int task_len=tasks.length;
        List<int[]> taskList=new ArrayList<>();
        for (int i = 0; i < tasks.length; i++) {
            int[] task=tasks[i];
            taskList.add(new int[]{task[0],task[1],i});
        }
        PriorityQueue<Integer> pq=new PriorityQueue<>((a,b)->{
            if(taskList.get(a)[1]!=taskList.get(b)[1])
                return  taskList.get(a)[1]-taskList.get(b)[1];
            return taskList.get(a)[2]-taskList.get(b)[2];
        });
        taskList.sort((a,b)->{
            if(a[0]!=b[0]){
                return a[0]-b[0];
            }
            return a[1]-b[1];
        });
        int[] ans=new int[task_len];
        //当前处理的时刻
        int now=0;
        //当前任务的索引
        int i=0;
        int idx=0;
        while (idx<task_len){
            if(!pq.isEmpty()){
                Integer poll = pq.poll();
                ans[idx++]=taskList.get(poll)[2];
                now+=taskList.get(poll)[1];
            }
            else if(i<task_len&& taskList.get(i)[0]>now ){
                now=taskList.get(i)[0];
            }
            for (;i<task_len&& taskList.get(i)[0]<=now;i++){
                pq.offer(i);
            }
        }
        return ans;

    }
    //https://leetcode.cn/problems/seat-reservation-manager/
    class SeatManager {

        PriorityQueue<Integer> pq;
        public SeatManager(int n) {
          pq=new PriorityQueue<>(n);
            for (int i = 1; i <= n; i++) {
                pq.offer(i);
            }
        }

        public int reserve() {
           return pq.poll();
        }

        public void unreserve(int seatNumber) {
            pq.offer(seatNumber);
        }
    }
   //https://leetcode.cn/problems/peeking-iterator/
    class PeekingIterator implements Iterator<Integer> {
       Integer nextEle;
       private final Iterator<Integer> iterator;

       public PeekingIterator(Iterator<Integer> iterator) {
           // initialize any member here.
           nextEle = iterator.next();
           this.iterator = iterator;
       }

       // Returns the next element in the iteration without advancing the iterator.
       public Integer peek() {
           return nextEle;
       }

       // hasNext() and next() should behave the same as in the Iterator interface.
       // Override them if needed.
       @Override
       public Integer next() {
           Integer retEle = nextEle;
           if (iterator.hasNext()) nextEle = iterator.next();
           else nextEle = null;
           return retEle;
       }

       @Override
       public boolean hasNext() {
           return nextEle!=null;
       }
    }
   //https://leetcode.cn/problems/flatten-nested-list-iterator/
    public interface NestedInteger {

       // @return true if this NestedInteger holds a single integer, rather than a nested list.
       public boolean isInteger();

       // @return the single integer that this NestedInteger holds, if it holds a single integer
       // Return null if this NestedInteger holds a nested list
       public Integer getInteger();

       // @return the nested list that this NestedInteger holds, if it holds a nested list
       // Return empty list if this NestedInteger holds a single integer
       public List<NestedInteger> getList();
   }

    public class NestedIterator implements Iterator<Integer> {
        private LinkedList<NestedInteger> queue;
        public NestedIterator(List<NestedInteger> nestedList) {
            queue=new LinkedList<>();
            for (NestedInteger nestedInteger : nestedList) {
                if(isNullorEmpty(nestedInteger)) continue;
                queue.offerLast(nestedInteger);
            }
        }

        private boolean isNullorEmpty(NestedInteger nestedInteger) {
           if(nestedInteger==null) return true;
           if(nestedInteger.isInteger()) return false;
           return nestedInteger.getList().stream().allMatch(x->isNullorEmpty(x));
        }

        @Override
        public Integer next() {
            NestedInteger nestedInteger = queue.pollFirst();
            if(nestedInteger.isInteger()) return nestedInteger.getInteger();
            List<NestedInteger> list = nestedInteger.getList();
            for (NestedInteger item : list
                    .reversed()) {
                if (isNullorEmpty(item)) continue;
                queue.offerFirst(item);
            }
            return next();
        }

        @Override
        public boolean hasNext() {
          return !queue.isEmpty();
        }
    }
     //https://leetcode.cn/problems/insert-delete-getrandom-o1/
    class RandomizedSet {
        List<Integer> list;
        Map<Integer,Integer> val_to_idx;
         Random random;
        public RandomizedSet() {
           list=new ArrayList<>();
           val_to_idx =new HashMap<>();
           random=new Random();
        }

        public boolean insert(int val) {
            if (val_to_idx.containsKey(val)) return false;
            list.add(val);
            val_to_idx.put(val, list.size() - 1);
            return true;
        }

        public boolean remove(int val) {
            if(!val_to_idx.containsKey(val)) return false;
            Integer remove_idx = val_to_idx.get(val);
            Integer last_val=list.get(list.size()-1);
            SwapElem(list,remove_idx,list.size()-1);
            val_to_idx.put(last_val,remove_idx);
            list.removeLast();
            val_to_idx.remove(val);
            return true;
        }

         private void SwapElem(List<Integer> list, Integer i, Integer j) {
             if(i.equals(j)) return;
             Integer temp = list.get(i);
             list.set(i, list.get(j));
             list.set(j, temp);
         }

         public int getRandom() {
          return list.get(random.nextInt(list.size()));
        }
    }
     //https://leetcode.cn/problems/random-pick-with-blacklist/
    class BlackListSolution {
         Map<Integer, Integer> black_map;
         Random random;
         int scope;
         public BlackListSolution(int n, int[] blacklist) {
             black_map = new HashMap<>();
             random = new Random();
             scope = n - blacklist.length;
             HashSet<Integer> black_set = new HashSet<>(blacklist.length);
             for (int black : blacklist) {
                 black_set.add(black);
             }

             int last=n-1;
             for (int black : blacklist) {
                 if(black<scope){
                     //ensure last is not black num
                     while (black_set.contains(last)) {
                         last--;
                     }
                   black_map.put(black,last--);
                 }
             }
         }
        public int pick() {
            int pick = random.nextInt(scope);
            return black_map.getOrDefault(pick, pick);
        }
    }

//    给出数字个数n和行数m（0 < n ≤ 999，0 < m ≤ 999），从左上角的1开始，按照顺时针螺旋向内写方式，依次写出2,3...n，最终形成一个m行矩阵。
//    对这个矩阵有些要求：
//            1.每行数字的个数一样多
//2.列的数量尽可能少
//3.填充数字时优先填充外部
//4.数字不够时，使用单个*号占位
//    输入描述：两个整数，空格隔开，依次表示n、m
//    输出描述：符合要求的唯一矩阵
    public String[][] printMatrix(int n,int m){
        //判断矩阵的列是多少
        int r=m;
        int c= n%m==0?n/m:n/m+1;
        String[][] matrix=new String[r][c];
        int start=0;
        int i=0,j=0,dir=0;
        int leftbound=0,rightbound=c-1,topbound=0,bottombound=r-1;
        for (int a = 0; a < r; a++) {
            for (int b = 0; b < c; b++) {
                matrix[a][b] = "*";
            }
        }
        while (start++<=n){
            matrix[i][j]= Integer.toString(start);
            if(dir==0){
                if(j==rightbound){
                    dir=1;
                    topbound++;
                    i++;
                }
                else j++;
            }
            else if(dir==1){
                if(i==bottombound){
                    dir=2;
                    rightbound--;
                    j--;
                }
                else i++;
            }
            else if(dir==2){
                if(j==leftbound){
                    dir=3;
                    bottombound--;
                    i--;
                }
                else j--;
            }
            else if(dir==3){
                if(i==topbound){
                    dir=0;
                    leftbound++;
                    j++;
                }
                else i--;
            }

        }
        return matrix;
    }

    //https://leetcode.cn/problems/random-flip-matrix/
    class FlipSolution {

        private final int m;
        private final int n;
        private Map<Integer,Integer> deletedMap;
        private Random random;
        private int len;
        public FlipSolution(int m, int n) {
            this.m = m;
            this.n = n;
            deletedMap = new HashMap<>();
            random = new Random();
            len=m*n;
        }

        public int[] flip() {
            int ran_idx = random.nextInt(len);
            int ret=ran_idx;
            if(deletedMap.containsKey(ran_idx)){
                ret= deletedMap.get(ran_idx);
            }
            //这个ran_idx 需要加入黑名单
            int last=len-1;
            if(deletedMap.containsKey(last)){
                last=deletedMap.get(last);
            }
            deletedMap.put(ran_idx,last);
            len--;
            return get(ret);
        }

        public void reset() {
             deletedMap.clear();
             len=m*n;
        }
      private  int[] get(int idx){
            return  new int[]{idx/n,idx%n};
      }
    }
   //https://leetcode.cn/problems/lfu-cache/
    //lfu 按照频次排序，如果频次一样的，就按照lru算法
    class LFUCache {
       private final int capacity;
       Map<Integer, Integer> key_freq;
        Map<Integer,Integer> key_value;
        Map<Integer,LinkedHashSet<Integer>> freq_key;
        int minFreq;
        public LFUCache(int capacity) {
            this.capacity = capacity;
            key_freq = new HashMap<>();
            key_value = new HashMap<>();
            freq_key = new HashMap<>();
            minFreq = 0;
        }

        public int get(int key) {
            if(!key_value.containsKey(key)) return -1;
            increseFreq(key);
            return key_value.get(key);
        }

       private void increseFreq(int key) {
           int freq=key_freq.get(key);
           if(!freq_key.containsKey(freq+1)) freq_key.put(freq+1,new LinkedHashSet<>());
           freq_key.get(freq+1).addLast(key);
           freq_key.get(freq).remove(key);
           key_freq.put(key,freq+1);
           if(freq_key.get(freq).isEmpty()) {
               freq_key.remove(freq);
               if(freq==minFreq) minFreq++;
           }
       }

       public void put(int key, int value) {
           if(key_value.containsKey(key)) {
               key_value.put(key,value);
               increseFreq(key);
           }
           else{
               if (capacity == key_value.size()) {
                   //需要把最少访问的干掉
                   LinkedHashSet<Integer> leastFreq = freq_key.get(minFreq);
                   Integer deleteKey = leastFreq.removeFirst();
                   if(leastFreq.isEmpty())
                       freq_key.remove(minFreq);
                   key_value.remove(deleteKey);
                   key_freq.remove(deleteKey);
               }
               freq_key.putIfAbsent(1,new LinkedHashSet<>());
               freq_key.get(1).addLast(key);
               key_value.put(key,value);
               key_freq.put(key,1);
               minFreq=1;
           }
        }
    }
   //https://leetcode.cn/problems/maximum-frequency-stack/
    class FreqStack {
       Map<Integer, Integer> key_freq;
       Map<Integer, Stack<Integer>> freq_key;
       //Stack<Integer> stk;
       int maxFreq;

       public FreqStack() {
           key_freq = new HashMap<>();
           freq_key = new HashMap<>();
           //stk = new Stack<>();
           maxFreq = 0;
       }

       public void push(int val) {
           //stk.push(val);
           int curFreq;
           curFreq = key_freq.getOrDefault(val, 0);
           key_freq.put(val, curFreq + 1);
           freq_key.putIfAbsent(curFreq + 1, new Stack<>());
           freq_key.get(curFreq + 1).addLast(val);
           maxFreq = Math.max(maxFreq, curFreq + 1);
       }

        public int pop() {
            int cur_maxFreq = maxFreq;
            Stack<Integer> maxFreqVals = freq_key.get(maxFreq);
            Integer ret = maxFreqVals.removeLast();
            if(maxFreqVals.isEmpty()) {
                freq_key.remove(maxFreq);
                //因为ret 的freq 的逻辑已经会-1，所以下面这个maxFreq --一定不会落空，这个和lfu 其实是有点异曲同工之妙
                maxFreq--;
            }
            //freq 需要降低
            key_freq.put(ret, cur_maxFreq-1);
            if (key_freq.get(ret) == 0) {
                key_freq.remove(ret);
            }
            return ret;
        }
    }
    public void run() {
        //var matrix = new NumMatrix(new int[][]{new int[]{1, 2}, new int[]{3, 4}});
        //var ans = matrix.sumRegion(0, 0, 1, 1);
        SolutionofFindSmallestRegion solutionofFindSmallestRegion = new SolutionofFindSmallestRegion();
//        String region = solutionofFindSmallestRegion.findSmallestRegion(Arrays.asList(
//                Arrays.asList("Earth", "North America", "South America"),
//                Arrays.asList("North America", "United States", "Canada"),
//                Arrays.asList("United States", "New York", "Boston"),
//                Arrays.asList("Canada", "Ontario", "Quebec"),
//                Arrays.asList("South America", "Brazil")
//        ), "Canada", "South America");
//        int[][] mat = new SolutionofMatrixBlockSum().matrixBlockSum(new int[][]{
//                new int[]{1,2,3},
//                new int[]{4,5,6},
//                new int[]{7,8,9}
//        },1);
        //var ans = new SolutionofMaxSubArrayLen().maxSubArrayLen(new int[]{1, -1, 5, -2, 3}, 3);
//        var ans=subarraySum(new int[]{1},0);
       //var ans=new SolutionofCountRangeSum().countRangeSum(new int[]{0,0},0,0);
        //var ans=countSmaller(new int[]{4,3,2,1});
       //var ans=new SolutionofStatisticalResult().statisticalResult(new int[]{2,4,6,8,10});
        //var ans=new SolutionofCarPolling().carPooling(new int[][]{new int[]{2,1,5},new int[]{3,5,7}},3);
       //var ans=longestValidParentheses("(()()(())((");
        //var ans=longestOnes(new int[]{0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1},3);
          //var ans= simplifyPath("/a/./b/../../c/");
        //var ans=findKthLargest(new int[]{2,1},1);
        //var ans=topKFrequent(new int[]{1,1,1,2,2,3},2);
        //var ans=pack(new int[]{1,3,4},new int[]{15,20,30},4);  // expect 35
        //var ans=topKFrequent(new String[]{"i","love","leetcode","i","love","coding"},3);  // expect 35
        //var ans=getOrder(new int[][]{new int[]{7,10},new int[]{7,12},new int[]{7,5},new int[]{7,4},new int[]{7,2}});  // expect 35
       //var ans=printMatrix(9,4);
//        var solution = new FlipSolution(3,1);
//        for (int i = 0; i < 10; i++) {
//            var ans=solution.flip();
//            ans=solution.flip();
//            ans=solution.flip();
//            solution.reset();
//        }
        //2],[1,1],[2,2],[1],[3,3],[2],[3],[4,4],[1],[3],[4]]
        var solution = new FreqStack();
        solution.push(5);
        solution.push(7);
        solution.push(5);
        solution.push(7);
        solution.push(4);
        solution.push(5);
        var ans=solution.pop();
        ans=solution.pop();
        ans=solution.pop();
        ans=solution.pop();
    }
}


